package zwp.exercise.intereview.base.sort;

import java.util.Arrays;

/**
 * @Author zwp14
 * @create 2024/6/27 22:14
 * @description 选择排序 -- 不稳定排序
 * 选出最小的元素,与所有元素进行比较,
 * 将数组分为两个子集,排序的和未排序的,
 * 每一轮从未排序的子集中选择最小的元素放进排序的子集中,重复以上的步骤,直到整个数组有序
 */
public class SelectionSort {
    public static void main(String[] args) {
        int[] a = {5, 9, 7, 4, 1, 3, 2, 8};
        System.out.println("未进行选择排序之前:" + Arrays.toString(a));
        int[] b = method(a);
        System.out.println("选择排序之后:" + Arrays.toString(b));
    }

    private static int[] method(int[] a) {
        //每一轮排序
        for (int i = 0; i < a.length - 1; i++) {
            //假设最小的数字为当前的索引0
            int minIdx = i;
            for (int j = minIdx + 1; j < a.length; j++) {
                //每一次排序,拿着假设最小的数去和其余所有的数进行比较,如果有比他小的则标记为最小数索引
                if (a[minIdx] > a[j]) {
                    minIdx = j;
                }
            }
            //将最小索引数和0索引数交换位置达到排序的效果
            if (minIdx != i){
                exchange(a, i, minIdx);
            }
            System.out.println(Arrays.toString(a));
        }
        return a;
    }

    private static void exchange(int[] a, int i, int minIdx) {
        int temp = a[i];
        a[i] = a[minIdx];
        a[minIdx] = temp;
    }
}
